/*
 * @lc app=leetcode.cn id=221 lang=javascript
 *
 * [221] 最大正方形
 */

// @lc code=start
/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    if (matrix.length == 0) return 0
    let r = matrix.length, c = matrix[0].length
    let dp = new Array(c)
    for (let i = 0; i < r; i++) dp[i] = new Array(c).fill(0)
    
    let ans = 0
    for (let i = 0; i < r; i++) {
        for (let j = 0; j < c; j++) {
            if (i-1 < 0 || j-1 < 0) {
                dp[i][j] = +matrix[i][j]
            } else {
                if (matrix[i][j] == 0) dp[i][j] = 0
                else {
                    let a = dp[i-1][j]
                    let b = dp[i][j-1]
                    let c = dp[i-1][j-1]
                    dp[i][j] = Math.min(Math.min(a, c), Math.min(b, c)) + 1
                }
            }
            if (dp[i][j] > ans) ans = dp[i][j]
        }
    }
    return ans ** 2
};
// @lc code=end

